package com.yileiqian.alg;

public class MaxSumInSubArray {

	public static int DP(int[] array) {
		int nStart = array[0];
		int nAll = array[0];

		for (int i = 1; i < array.length; i++) {
			nStart = Math.max(array[i], nStart + array[i]);
			nAll = Math.max(nStart, nAll);
		}
		return nAll;
	}

	public static void main(String args[]) {
		int array[] = { -2, 5, 3, -3, 4, -8, 6 };
		System.out.println(DP(array));
	}
}
